#include "millerRabinTest.h"

bool MillerRabinTest::isPrimNumber(quint64 number)
{
    // test obviously result
    if(number < 2)
        return false;

    if(number ==  2 || number == 3)
        return true;

    if((number & 1) == 0)
        return false;

    // test using Miller-Rabin

    // find k, q so that n = 2^k*q + 1
    quint64 k = 0;
    quint64 q = number - 1;

    while(0 == (q & 1))
    {
        q >>= 1;
        ++k;
    }

    if(number < 1373653)
    {
        if(runMillerRabin(2, k, q, number)
           || runMillerRabin(3, k, q, number))
            return false;

    }else if(number < 9080191)
    {
        if(runMillerRabin(31, k, q, number)
           || runMillerRabin(73, k, q, number))
            return false;

    }else if(number < 4759123141)
    {
        if(runMillerRabin(2, k, q, number)
           || runMillerRabin(3, k, q, number)
           || runMillerRabin(5, k, q, number)
           || runMillerRabin(11, k, q, number))
            return false;

    }else if(number < 2152302898747)
    {
        if(runMillerRabin(2, k, q, number)
           || runMillerRabin(3, k, q, number)
           || runMillerRabin(5, k, q, number)
           || runMillerRabin(7, k, q, number)
           || runMillerRabin(11, k, q, number))
            return false;

    }else
    {
        if(runMillerRabin(2, k, q, number)
           || runMillerRabin(3, k, q, number)
           || runMillerRabin(5, k, q, number)
           || runMillerRabin(7, k, q, number)
           || runMillerRabin(11, k, q, number)
           || runMillerRabin(31, k, q, number)
           || runMillerRabin(61, k, q, number)
           || runMillerRabin(73, k, q, number))
            return false;
    }

    return true;
}

quint64 MillerRabinTest::runMontgomery(quint64 a, quint64 b, quint64 number)
{
    quint64 r   = a % number;
    quint64 tmp = 1;

    while(b > 1)
    {
        if((b & 1) != 0)
        {
            tmp = (tmp * r) % number;
        }

        r = (r * r) % number;

        b >>= 1;
    }

    return (r * tmp) % number;
}

bool MillerRabinTest::runMillerRabin(quint64 a, quint64 k, quint64 q, quint64 n)
{
    if( 1 != runMontgomery(a, q, n))
    {
        quint64 e = 1;

        for(quint64 i = 0; i < k; ++i)
        {
            if((n-1) == runMontgomery(a, q * e, n))
                return false;

            e <<= 1;
        }

        return true;
    }

    return false;
}
